#include <vector>
#include <ext/numeric>
#include <stdlib.h>
#include <assert.h>
#include <iostream>
#include <algorithm>
#include <iterator>
#include <functional>

using namespace std;
typedef vector<unsigned> Unsigneds;
typedef Unsigneds::iterator UnsIterator;

template <class Compare>
UnsIterator partition( UnsIterator begin, UnsIterator end, Compare const &c ){
    if ( end == begin ) return end;
    UnsIterator i(begin), j(end-1);
    while ( i < j ) {
	while ( i < end && c(*i) ) i++;
	while ( j > begin && !c(*j) ) j--;
	if ( i < j ) swap( *i++, *j-- );
    }
    while ( i < end && c(*i) ) i++;
    return i;
}

template <class Compare>
bool check_partition( UnsIterator begin, UnsIterator end, 
		      UnsIterator transition,
		      Compare const &c ){
    while ( begin < end && begin < transition ) {
	if ( !c(*begin) ) return false;
	begin++;
    }
    while ( begin < end ) {
	if ( c(*begin) ) return false;
	begin++;
    }
    return true;
}

void check_compares( Unsigneds usA, unsigned pivot ) {
    unsigned max(*(max_element( usA.begin(), usA.end() ) ));
    unsigned min(*(min_element( usA.begin(), usA.end() ) ));

    {
	Unsigneds us(usA);
	binder2nd<less<unsigned > > 
	    compare(bind2nd(less<unsigned>(), pivot));
	UnsIterator it = partition( us.begin(), us.end(), compare );
	assert( check_partition( us.begin(), us.end(), it, compare ) );
	us = usA;
	compare = bind2nd(less<unsigned>(), max+1);
	it = partition( us.begin(), us.end(), compare );
	assert( it == us.end() );
	assert( check_partition( us.begin(), us.end(), it, compare ) );
	us = usA;
	compare = bind2nd(less<unsigned>(), min-1);
	it = partition( us.begin(), us.end(), compare );
	assert( it == us.begin() );
	assert( check_partition( us.begin(), us.end(), it, compare ) );
    }

    {
	Unsigneds us(usA);
	binder2nd<less_equal<unsigned > > 
	    compare(bind2nd(less_equal<unsigned>(), pivot));
	UnsIterator it = partition( us.begin(), us.end(), compare );
	assert( check_partition( us.begin(), us.end(), it, compare ) );
	us = usA;
	compare = bind2nd(less_equal<unsigned>(), max+1);
	it = partition( us.begin(), us.end(), compare );
	assert( it == us.end() );
	assert( check_partition( us.begin(), us.end(), it, compare ) );
	us = usA;
	compare = bind2nd(less_equal<unsigned>(), min-1);
	it = partition( us.begin(), us.end(), compare );
	assert( it == us.begin() );
	assert( check_partition( us.begin(), us.end(), it, compare ) );
    }
    {
	binder2nd<greater<unsigned> >
	    compare(bind2nd(greater<unsigned>(),pivot));
	Unsigneds us(usA);
	UnsIterator it = partition( us.begin(), us.end(), compare );
	assert( check_partition( us.begin(), us.end(), it, compare ) );
	us = usA;
	compare = bind2nd(greater<unsigned>(),max+1);
	it = partition( us.begin(), us.end(), compare );
	assert( it == us.begin() );
	assert( check_partition( us.begin(), us.end(), it, compare ) );
	us = usA;
	compare = bind2nd(greater<unsigned>(),min-1);
	it = partition( us.begin(), us.end(), compare );
	assert( it == us.end() );
	assert( check_partition( us.begin(), us.end(), it, compare ) );
    }
    {
	binder2nd<greater_equal<unsigned> >
	    compare(bind2nd(greater_equal<unsigned>(), pivot));
	Unsigneds us(usA);
	UnsIterator it = partition( us.begin(), us.end(), compare );
	assert( check_partition( us.begin(), us.end(), it, compare ) );
	us = usA;
	compare = bind2nd(greater_equal<unsigned>(), max+1);
	it = partition( us.begin(), us.end(), compare );
	assert( it == us.begin() );
	assert( check_partition( us.begin(), us.end(), it, compare ) );
	us = usA;
	compare = bind2nd(greater_equal<unsigned>(),min-1);
	it = partition( us.begin(), us.end(), compare );
	assert( it == us.end() );
	assert( check_partition( us.begin(), us.end(), it, compare ) );
    }
    {
	binder2nd<equal_to<unsigned> >
	    compare(bind2nd(equal_to<unsigned>(),pivot));
	Unsigneds us(usA);
	UnsIterator it = partition( us.begin(), us.end(), compare );
	assert( check_partition( us.begin(), us.end(), it, compare ) );
	us = usA;
	compare = bind2nd(equal_to<unsigned>(), max+1);
	it = partition( us.begin(), us.end(), compare );
	assert( it == us.begin() );
	assert( check_partition( us.begin(), us.end(), it, compare ) );
	us = usA;
	compare = bind2nd(equal_to<unsigned>(), min-1);
	it = partition( us.begin(), us.end(), compare );
	assert( it == us.begin() );
	assert( check_partition( us.begin(), us.end(), it, compare ) );
    }
    {
	binder2nd<not_equal_to<unsigned> >
	    compare(bind2nd(not_equal_to<unsigned>(), pivot));
	Unsigneds us(usA);
	UnsIterator it = partition( us.begin(), us.end(), compare );
	assert( check_partition( us.begin(), us.end(), it, compare ) );
	us = usA;
	compare = bind2nd(not_equal_to<unsigned>(), max+1);
	it = partition( us.begin(), us.end(), compare );
	assert( it == us.end() );
	assert( check_partition( us.begin(), us.end(), it, compare ) );
	us = usA;
	compare = bind2nd(not_equal_to<unsigned>(), min-1);
	it = partition( us.begin(), us.end(), compare );
	assert( it == us.end() );
	assert( check_partition( us.begin(), us.end(), it, compare ) );
    }
}

int main( int argc, char *argv[] ) {
    unsigned seed( time(NULL) % 100000 );
    if ( argc > 1 ) {
	seed = atoi( argv[1] );
    }
    cout << "seed : " << seed << endl;
    srand( seed );

    unsigned iterations = 1000;
    while ( iterations-- ) {
	Unsigneds us(1000);
	iota( us.begin(), us.end(), 1 );
	random_shuffle( us.begin(), us.end() );
	const unsigned pivot( us.size() ? us[us.size()/2] : 0 );
	check_compares( us, pivot );
    }

    {
	Unsigneds us( 1 );
	us[0] = 1;

	check_compares( us, 0 );
	check_compares( us, 1 );
	check_compares( us, 2 );
    }
    {
	Unsigneds us( 2 );
	us[0] = 1;
	us[1] = 2;

	check_compares( us, 0 );
	check_compares( us, 1 );
	check_compares( us, 2 );
	check_compares( us, 3 );
    }

    return 0;
}
